package LinkedListSorted;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-08
 * Time: 14:40
 */


class ListNode {
     int val;
     ListNode next;
     public ListNode(int val){
         this.val = val;
     }
   }

class Solution1 {
     public ListNode sortInList (ListNode head) {
         if (head == null ||
                 head.next == null) return head; //结点为空或只有一个结点
         return quickSort(head);
     }
     ListNode quickSort(ListNode head) {//链表快排，没有交换，排序稳定
         if (head == null ||
                 head.next == null) return head; //结点为空，或者只有一个结点
         //将链表分成三段，第一段都比枢轴小，第二段等于枢轴，第三段都大于枢轴
         ListNode lhead = new ListNode(-1); //第一段的虚头结点
         /* 这里提一下，注释里告诉我们ListNode类没有有参构造方法，但是new的新对象不加参数的话，
          * 代码放到牛客编译器里出错，必须加上参数val才正常,这是牛客的一个疏忽吧
          */
         ListNode mhead = new ListNode(-1); //第二段的虚头结点
         ListNode rhead = new ListNode(-1); //第三段的虚头结点
         ListNode left = lhead; //第一段的遍历指针
         ListNode mid = mhead; //第二段的遍历指针
         ListNode right = rhead; //第三段的遍历指针
         ListNode p = head; //原链表的遍历指针
         int pivot = head.val; //将第一个元素作为枢轴
         //不断划分
         while (p != null) {
             if (p.val < pivot) { //比枢轴小，挂到第一段链表末尾
                 left.next = p;
                 left = left.next;
             } else if (p.val == pivot) {
                 mid.next = p;
                 mid = mid.next;
             } else { //比枢轴大，挂到第三段链表末尾
                 right.next = p;
                 right = right.next;
             }
             p = p.next;
         }
         left.next = null; //断开后面的链
         mid.next = null; //断开后面的链
         right.next = null; //断开后面的链

         //递归对第一段和第三段进行排序；因为第二段各元素相等，不用再排序
         lhead.next = quickSort(lhead.next);
         rhead.next = quickSort(rhead.next);
         left = getTail(lhead); //获取链表最后一个元素
         if (left != null) left.next = mhead.next; //合并第一段和第二段
         mid = getTail(mhead); //获取链表最后一个元素
         if (mid != null) mid.next = rhead.next; //合并第二段和第三段
         return lhead.next;
     }
     ListNode getTail(ListNode head) {//获取给定链表的最后一个结点
         if (head == null) return null;
         while (head.next != null) { //不是最后一个结点就循环
             head = head.next;
         }
         return head;
     }
 }


class Solution {
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null)
            return head;
        // 使用快慢指针寻找链表的中点
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        // 递归左右两边进行排序
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);
        // 创建新的链表
        ListNode h = new ListNode(-1);
        ListNode res = h;
        // 合并 left right两个链表
        while (left != null && right != null) {
            // left  right链表循环对比
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        // 最后添加未对比的链表部分判断左链表是否为空
        h.next = left != null ? left : right;
        return res.next;
    }
}
public class TestSortLinkedList {

    public static void main(String[] args) {

    }

}
